package main.java.indi.zyj.coderecord;

import java.util.*;

public class LadderLength {

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        Set<String> wordSet = new HashSet<>(wordList);
        int size = wordSet.size();

        if (size == 0 || !wordSet.contains(endWord)) {
            return 0;
        }

        Deque<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        Map<String, Integer> trace = new HashMap<>();
        trace.put(beginWord, 1);

        while (!queue.isEmpty()) {

            String word = queue.poll();
            int length = word.length();
            int path = trace.get(word);
            for (int i = 0; i < length; i++) {
                char[] chars = word.toCharArray(); //将单词转换为char array，方便替换
                for (char k = 'a'; k <= 'z'; k++) { //从'a' 到 'z' 遍历替换
                    chars[i] = k; //替换第i个字符
                    String newWord = String.valueOf(chars); //得到新的字符串
                    if (newWord.equals(endWord)) {  //如果新的字符串值与endWord一致，返回当前长度+1
                        return path + 1;
                    }
                    if (wordSet.contains(newWord) && !trace.containsKey(newWord)) { //如果新单词在set中，但是没有访问过
                        trace.put(newWord, path + 1); //记录单词对应的路径长度
                        queue.offer(newWord);//加入队尾
                    }
                }
            }

        }

        return 0;

    }

}
